package com.javabasic.algorithm.cometoj;

import java.util.Scanner;

public class 沉鱼落雁 {
    static Scanner cin = new Scanner(System.in);

    public static void main(String[] args) {
        int n = cin.nextInt();
        long num;
        long Max = Long.MAX_VALUE/2;
        while (n-- > 0) {
            num = cin.nextLong();
            if (num == 1) {
                System.out.println("1");
                continue;
            } else if (num == 3) {
                System.out.println("2");
                continue;
            }
//            long l = 1, r = Max;
//            while (l <= r) {
//                long mid = (r-l)/2+l;
//                if ((mid+1)*mid/2 > num) {
//                    r = mid-1;
//                } else if ((mid+1)*mid/2 < num) {
//                    l = mid+1;
//                } else {
//                    System.out.println(mid);
//                    break;
//                }
//            }
            for (int i = 3; ;i++) {
                if (i%2 == 0) {
                    if (((i / 2) % num * (i + 1) % num) % num == 0) {
                        System.out.println(i);
                        break;
                    }
                } else {
                    if ((((i+1)/ 2) % num) * (i % num) % num == 0) {
                        System.out.println(i);
                        break;
                    }
                }
            }
        }
    }
}
